The aggregate link bandwidth for all links supported by a packet switching device (e.g., a router) is often higher than the total switching capacity of the device. This causes congestion at buffers located at the ingress (pre-stitching) and egress (post-switching) stages of the device. Congestion may even arise in switch fabrics that are non-blocking. Commonly, buffering may be used to control congestion. However, buffering may cause delays in the delivery of packets and therefore in order to avoid excessive delays, a more sophisticated technique for congestion needs to be developed.
One solution for controlling congestion is a tail drop approach, whereby an egress buffer is allowed to fill and then packets are dropped if they arrive from the switch fabric while the buffer is full. However, this approach may cause multiple flows to suffer lost packets. The higher layer protocols may react to this type of packet loss by terminating the flow and re-transmitting the lost information. Although congestion per se has been eliminated, the end result will be a highly undesirable slowdown-speedup-slowdown-etc. behaviour of the packet switching device.
In another conventional congestion control algorithms, the egress stage takes an action on each packet, such action being either to queue the packet or discard it. An example of an algorithm of this type is a random early discard (RED) algorithm. Specific examples of RED algorithms include the RED algorithm (described in Internet Request For Comments (RFC) 2309, April 1998, incorporated by reference herein) and the BLUE algorithm (described in “BLUE: A New Class of Active Queue Management Algorithms”, Wu-chang Feng et al., pages 1-26, incorporated by reference herein). The decision as to whether a packet should be discarded or queued is made by monitoring the degree to which the egress buffer on a given link is full and consequently generating a discard probability for that packet. If a random number generated for that packet is below the discard probability, the packet is discarded; otherwise it is placed in the egress buffer. In this way, congestion at the egress buffer can be controlled by actions taken at the egress buffer.
However, adding to jitter and latency by delaying packets that will not be discarded and sending packets that will be discarded requires switch fabrics to be significantly over-provisioned. Thus, by the very action of discarding or queuing a packet at the device egress (i.e., once switching resources have already been utilized to switch the packet), those packets that are eventually discarded will have unnecessarily consumed resources throughout the ingress and switching stages of the packet switching device. Clearly, by making decisions based on measured congestion levels, there will inevitably be an inefficiency regarding the extent to which the memory and/or switching resources of the devices are utilized.
Accordingly, there is a need in the industry to develop a mechanism that limits congestion while resulting in more efficient resource utilization within a packet switching device such as a router.